Data between a source node and a destination node in communications networks may be routed according to various routing protocols. One class of routing protocols is the link state protocol. In link state protocols, each node advertises information about its adjacent links and connectivity with other nodes. A link advertisement may be sent in a link state packet (“LSP”). Based on the advertised information included in the LSP, each node constructs a link state database (“LSDB”) that contains a map of the entire network topology. From the data stored in a LSDB, a node constructs a routing information base (“RIB”) that contains one or more routes to each available node in the network. The single optimum route to a node may be computed according to any of various algorithms, such as a shortest path first (“SPF”) algorithm. Based on the information stored in a RIB, a node constructs a forwarding information base (“FIB”) and uses the FIB to forward data packets to other nodes.
In a conventional link state protocol network, upon detecting that a network topology has changed, the nodes generate and disseminate new LSP advertisements that contain updated information about the nodes' connectivity. The LSP advertisements are received by other nodes and used by the nodes to update their routing databases.
However, generating, distributing and processing of the LSP advertisements, as well as updating a link state database, a routing information base and a forwarding information base at each node of the network are often time consuming and computationally complicated. Therefore, each time a network component fails, the network may be unstable for a relatively long period of time, during which the network tries to converge upon an agreed view of routing information in which nodes update their routing information.
Furthermore, as the network converges, routing databases may be temporarily de-synchronized and loops in data transmission may occur. For example, if a first node tries to send a data packet via a second node to a third node, but due to the network's de-synchronization, the second node determines that the best route to the third node is via the first node, then the second node sends the packet back to the first node, instead of forwarding the packet to the third node. This can continue until all nodes update their routing information, or unless some safety procedures are implemented, such as discarding the packet if a maximum hop count for the packet has been exceeded.
Bryant and Shand have proposed approaches in which each node generates a repair address for each of its protected neighbors in advance and advertises a particular repair addresses for a particular protected neighbor to other nodes. The particular repair address may be used by other nodes when the particular protected neighbor indeed fails. The repair address for the protected neighbor node is referred to as a not-via address. In one such approach, each node generates and advertises one not-via address for each of its protected neighbors, and each other node stores a not-via address for each of the protected components.